package ljl.codetop300;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 这个是 lis 的进阶版，更加的变态了
 */
public class _673_length_of_l_i_s {

  static class off1 {
    public int findNumberOfLIS(int[] nums) {
      int n = nums.length, maxLen = 0, ans = 0;
      int[] dp = new int[n];
      int[] cnt = new int[n];
      for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        cnt[i] = 1;
        for (int j = 0; j < i; ++j) {
          if (nums[i] > nums[j]) {
            if (dp[j] + 1 > dp[i]) {
              dp[i] = dp[j] + 1;
              cnt[i] = cnt[j];
            }
            else if (dp[j] + 1 == dp[i]) {
              cnt[i] += cnt[j];
            }
          }
        }
        if (dp[i] > maxLen) {
          maxLen = dp[i];
          ans = cnt[i];
        }
        else if (dp[i] == maxLen) {
          ans += cnt[i];
        }
      }
      return ans;
    }
  }

  /**
   * 背了一遍，我可不会啊，我可不会
   */
  static class copyoff1 {
    public int findNumberOfLIS(int[] nums) {
      int[] dp = new int[nums.length];
      int[] counts = new int[nums.length];
      int maxlen = 0;
      int maxCount = 0;
      for (int i = 0; i < nums.length; i++) {
        dp[i] = 1;
        counts[i] = 1;
        for (int j = 0; j < i; j++) {
          if (nums[j] < nums[i]) {
            if (dp[j] + 1 > dp[i]) {
              dp[i] = dp[j] + 1;
              counts[i] = counts[j];
            } else if (dp[j] + 1 == dp[i]) {
              counts[i] += counts[j];
            }
          }
        }
        if (dp[i] > maxlen) {
          maxlen = dp[i];
          maxCount = counts[i];
        } else if (dp[i] == maxlen) {
          maxCount += counts[i];
        }
      }
      return maxCount;
    }
  }

  /**
   * 阴间解法
   */
  static class off2 {
    /**
     * 好了每一行都看懂了，可是为什么是对的？
     */
    public int findNumberOfLIS(int[] nums) {
      List<List<Integer>> d = new ArrayList<>();
      List<List<Integer>> cnt = new ArrayList<>();

      for (int v : nums) {
        int i = binarySearch1(d, v);
        int c = 1;
        if (i > 0) {
          int k = binarySearch2(d.get(i - 1), v);
          // 为什么是 k 被减去而不是 k - 1，因为 cnt[i] 下标比 d[i] 要大 1，本来是一样的他改成前缀和了
          c = (cnt.get(i - 1).get(cnt.get(i - 1).size() - 1)) - (cnt.get(i - 1).get(k));
        }
        if (i == d.size()) {
          List<Integer> dList = new ArrayList<>();
          dList.add(v);
          d.add(dList);
          List<Integer> cntList = new ArrayList<>();
          cntList.add(0);
          cntList.add(c);
          cnt.add(cntList);
        }
        else {
          d.get(i).add(v);
          int cntSize = cnt.get(i).size();
          cnt.get(i).add(cnt.get(i).get(cntSize - 1) + c);
        }
      }

      // 返回 cnt[-1][-1]
      int size1 = cnt.size(), size2 = cnt.get(size1 - 1).size();
      return cnt.get(size1 - 1).get(size2 - 1);
    }

    /**
     * 找到第一个比 target 不小的列表位置
     */
    public int binarySearch1(List<List<Integer>> d, int target) {
      int l = 0, r = d.size();
      while (l < r) {
        int mid = (l + r) / 2;
        List<Integer> list = d.get(mid);
        if (list.get(list.size() - 1) >= target) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      return l;
    }

    /**
     * 找到第一个比 target 小的位置
     */
    public int binarySearch2(List<Integer> list, int target) {
      int l = 0, r = list.size();
      while (l < r) {
        int mid = (l + r) / 2;
        if (list.get(mid) < target) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      return l;
    }
  }

  static class copyoff2 {
    public int findNumberOfLIS(int[] nums) {
      List<List<Integer>> d = new ArrayList<>();
      List<List<Integer>> cnt = new ArrayList<>();
      for (int num : nums) {
        int i = searchFirstNotLessThan(d, num);
        int c = 1;
        if (i > 0) {
          int k = searchFirstLessThan(d.get(i - 1), num);
          c = last(cnt.get(i - 1)) - cnt.get(i - 1).get(k);
        }
        if (i == d.size()) {
          List<Integer> d0 = new ArrayList<>();
          d0.add(num);
          d.add(d0);
          List<Integer> cnt0 = new ArrayList<>();
          cnt0.add(0);
          cnt0.add(c);
          cnt.add(cnt0);
        } else {
          d.get(i).add(num);
          cnt.get(i).add(last(cnt.get(i)) + c);
        }
      }
      return last(last(cnt));
    }

    static <T> T last(List<T> list) {
      return list.get(list.size() - 1);
    }

    int searchFirstNotLessThan(List<List<Integer>> list, int value) {
      int l = 0, r = list.size();
      while (l < r) {
        int mid = (l + r) >>> 1;
        List<Integer> midList = list.get(mid);
        if (last(midList) >= value) r = mid;
        else l = mid + 1;
      }
      return l;
    }
    int searchFirstLessThan(List<Integer> list, int value) {
      int l = 0, r = list.size();
      while (l < r) {
        int mid = (l + r) >>> 1;
        if (list.get(mid) < value) r = mid;
        else l = mid + 1;
      }
      return l;
    }

  }
}
